package algotithm.jianzhioffer.test13;

/**
 * @author zhouyanxiang
 * @Date 2020-12-2020/12/14-17:04
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int count = solution.movingCount(2, 3, 1);
        System.out.println(count);
    }

    boolean[][] visited;
    int m, n, k;

    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }

    public int dfs(int i, int j, int si, int sj) {
        if (i >= m || j >= n || si + sj > k || visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, (si + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (sj + 1) % 10 != 0 ? sj + 1 : sj - 8);
    }
}
